package likou;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/19 08:05
 */
public class _1239 {
    public static void main(String[] args) {
        _1239 test = new _1239();
        ArrayList<String> strings = new ArrayList<>();
        strings.add("abcdefghijklmnopqrstuvwxyz");
        test.maxLength(strings);
    }
    // 保存原始字符串的信息
    static class Node {
        // 字符串压缩后的值
        final int val;
        // 字符串的字符个数
        final int len;
        Node(int val, int len) {
            this.val = val;
            this.len = len;
        }
    }

    int nodeNum = 0;

    public int maxLength(List<String> arr) {
        Node[] nodes = new Node[arr.size()];
        for (String str : arr) {
            // 将字符串压缩成整型值
            int val = getVal(str);
            if (val > 0) {
                nodes[nodeNum++] = new Node(val, str.length());
            }
        }
        return backtrack(nodes, 0, 0, 0);
    }

    //判断字符串是否包含重复字符
    private int getVal(String str) {
        int val = 0;
        for (int i = 0; i < str.length(); i++) {
            int ival = (1 << (str.charAt(i) - 'a'));
            // 字符串包含重复字符时，返回-1
            if ((val & ival) != 0) {
                return -1;
            }
            val |= ival;
        }
        return val;
    }

    /**
     * @param nodes 字符串预处理后的信息
     * @param depth 当前栈的深度
     * @param val 已连接字符串对应的整型值
     * @param len 已连接字符串的字符个数
     * @return 连接字符串最长长度
     */
    private int backtrack(Node[] nodes, int depth, int val, int len) {
        if (nodeNum <= depth) {
            return len;
        }
        // 不连接当前字符串
        int bt1 = backtrack(nodes, depth + 1, val, len);
        // 判断当前字符串是否可以跟已连接的字符串连接，通过预处理优化
        if ((nodes[depth].val + val) == (nodes[depth].val | val)) {
            // 连接当前字符串，通过预处理优化
            int bt2 = backtrack(nodes, depth + 1, val + nodes[depth].val, len + nodes[depth].len);
            return Math.max(bt1, bt2);
        }
        return bt1;
    }
}
